package william.list;

/**
 * @author ZhangShenao
 * @date 2024/1/14
 * @description <a href="https://leetcode.cn/problems/palindrome-linked-list/description/">...</a>
 */
public class Leetcode234_回文链表 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * Step1:通过快、慢双指针法,快指针每次前进2个节点,慢指针每次前进1个节点。当快指针移动到链表末尾时,慢指针指向链表后半部分的头节点
     * Step2:将链表后半部分反转
     * Step3:将快指针重置到链表头结点
     * Step4:将快、慢指针同时向前移动,依次比较每个节点的值是否相同
     */
    public boolean isPalindrome(ListNode head) {
        //边界条件校验
        if (head == null) {
            return true;
        }

        //通过快、慢双指针法,找到链表后半部分的头节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //如果链表节点数量为奇数个,则最后fast!=null,slow需要再前进一个节点
        if (fast != null) {
            slow = slow.next;
        }

        //slow为链表后半部分的头节点,将链表后半部分反转
        slow = reverse(slow);

        //将fast重置到链表头节点
        fast = head;

        //将快、慢指针同时向前移动,依次比较每个节点的值是否相同
        while (slow != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }

        return true;
    }

    /**
     * 将以head为头结点的链表反转,并返回反转后的链表头结点
     */
    private ListNode reverse(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}
